class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
// 创建根节点
const root = new TreeNode("A");
// 创建第二层节点
root.left = new TreeNode("B");
root.right = new TreeNode("C");
// 创建第三层节点
root.left.left = new TreeNode("D");
root.left.right = new TreeNode("E");
root.right.left = new TreeNode("F");
root.right.right = new TreeNode("G");
// 创建第四层节点
root.left.left.left = new TreeNode("H");
root.left.left.right = new TreeNode("I");
/*
 *        A
 *      /   \
 *     B     C
 *    / \   / \
 *   D   E F   G
 *  / \
 * H   I
 */
function depthFirstSearch(root, target) {
    if (root === null) {
        return false;
    }

    console.log("Visiting node:", root.value); // 打印当前访问的节点

    if (root.value === target) {
        console.log("Found target:", target);  // 打印找到目标
        return true;
    }

    const leftResult = depthFirstSearch(root.left, target);
    if (leftResult) return true;  // 如果左子树找到，提前返回，避免不必要的右子树搜索

    return depthFirstSearch(root.right, target);
}

console.log(depthFirstSearch(root,"C"));
